#pragma once
#include "common.h"

namespace redisStruct
{
	template <class T>
	struct HashTableNode
	{
		T _val;
		HashTableNode<T>* _next = nullptr;

		HashTableNode()
		{}
		HashTableNode(const T& val) : _val(val)
		{}
	};
	template <class Key, class T, class KOfT, class HashFunc, class EqualOfK, class Ptr, class Ref, class CopyOfT, class FreeOfT>
	class _HT_Iterator;
	/*
	 * Key
	 * T: 节点存储的类型
	 * KOfT: 用来获取T类型对象中的Key类型对象
	 * HashFunc: 哈希算法
	 * EqualOfK: 比较key类型对象是否相等
	 * CopyOfT: 用来拷贝T //牵扯到引用计数时需要定制仿函数
	 * FreeOfT: 用来释放T
	 */
	template <class Key, class T, class KOfT, class HashFunc, class EqualOfK, class CopyOfT, class FreeOfT>
	class HashTable
	{
		typedef HashTableNode<T> Node;

		template <class Key1, class T1, class KOfT1, class HashFunc1, class EqualOfK1, class Ptr1, class Ref1, class CopyOfT1, class FreeOfT1>
		friend class _HT_Iterator;

	public:
		typedef _HT_Iterator<Key, T, KOfT, HashFunc, EqualOfK, T*, T&, CopyOfT, FreeOfT> iterator;
		typedef _HT_Iterator<Key, T, KOfT, HashFunc, EqualOfK, const T*, const T&, CopyOfT, FreeOfT> const_iterator;

	private:
		size_t _used_nums = 0;	  // 总共键值对
		size_t _bucket_nums = 10; // 桶数,默认从10开始  负载因子 == _used_nums/_bucket_nums ，>=1时扩容，扩二倍

		vector<Node*> _tables;
		// vector<Node*> _aux_tables;//rehash时的辅助
		// bool rehashing = false;
	public:
		HashTable() : _tables(_bucket_nums, nullptr)
		{
		}
		HashTable(HashTable& other)
		{
			_tables.resize(other._bucket_nums, nullptr);
			for (int i = 0; i < other._bucket_nums; i++)
			{
				Node* cur = other._tables[i];
				insert(cur->_val);
				cur = cur->_next;
			}
		}
		~HashTable()
		{
			for (int i = 0; i < _bucket_nums; i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					FreeOfT()(cur->_val);
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}
        
		size_t size() const
		{
			return _used_nums;
		}
		HashTable& operator=(HashTable& other)
		{
			std::swap(_used_nums, other._used_nums);
			std::swap(_bucket_nums, other._bucket_nums);
			_tables.swap(other._tables);
			return *this;
		}

		iterator begin()
		{
			Node* cur = nullptr;
			for (int i = 0; i < _bucket_nums; i++)
				if (_tables[i] != nullptr)
				{
					cur = _tables[i];
					break;
				}
			return iterator(this, cur);
		}
		const_iterator begin() const
		{
			Node* cur = nullptr;
			for (int i = 0; i < _bucket_nums; i++)
				if (_tables[i] != nullptr)
				{
					cur = _tables[i];
					break;
				}
			return const_iterator(this, cur);
		}
		iterator end()
		{
			return iterator(this, nullptr);
		}
		const_iterator end() const
		{
			return const_iterator(this, nullptr);
		}

		iterator find(const Key& key)
		{
			KOfT koft;
			EqualOfK kIsEqual;

			int pos = HashFunc()(key) % _bucket_nums;

			Node* cur = _tables[pos];
			while (cur)
			{
				if (kIsEqual(key, koft(cur->_val))) // 找到了
					return iterator(this, cur);
				cur = cur->_next;
			}

			return iterator(this, nullptr);
		}

		pair<iterator, bool> insert(const T& val)
		{
			HashFunc hfc;
			KOfT koft; // 拿到T中的K类型对象

			iterator ret = find(KOfT()(val));
			if (ret != end())
				return make_pair(ret, false);

			// 是否需要扩容
			if (_used_nums >= _bucket_nums)
			{ // 扩容逻辑
				size_t newsize = _bucket_nums * 2;
				vector<Node*> newTables(newsize, nullptr);
				// 遍历旧表所有桶
				for (int i = 0; i < _bucket_nums; i++)
				{
					// 遍历桶内单链表所有节点
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						int newPos = hfc(koft(cur->_val)) % newsize;
						cur->_next = newTables[newPos];
						newTables[newPos] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newTables);
				_bucket_nums = newsize;
			}

			// 插入逻辑

			int pos = hfc(koft(val)) % _bucket_nums;
			Node* node = new Node(CopyOfT()(val));
			node->_next = _tables[pos]; // 头插
			_tables[pos] = node;
			_used_nums++;

			return make_pair(iterator(this, node), true);
		}

		// 渐进式rehash
		/*pair<iterator, bool> insert(const T&)
		{

		}*/

		iterator erase(const Key& key)
		{
			KOfT koft;
			EqualOfK kIsEqual;

			int pos = HashFunc()(key) % _bucket_nums;

			Node* prev = nullptr;
			Node* cur = _tables[pos];
			while (cur)
			{
				if (kIsEqual(key, koft(cur->_val))) // 找到了
				{
					if (prev)
					{
						prev->_next = cur->_next;
					}
					else
					{ // 删除的是头结点
						_tables[pos] = cur->_next;
					}
					iterator iter(this, cur);
					iter++;
					FreeOfT()(cur->_val);
					delete cur;
					_used_nums--;
					return iter;
				}
				prev = cur;
				cur = cur->_next;
			}

			return iterator(this, nullptr);
		}
	};
	/******************HashFunc*************/

	template <class T>
	struct Hash
	{
		size_t operator()(const T& t)
		{
			return t;
		}
	};
	// string版本
	/*template <>
	struct Hash<string>
	{
		size_t operator()(const string& str)
		{
			// BKDR
			size_t value = 0;
			for (auto ch : str)
			{
				value *= 31;
				value += ch;
			}
			return value;
		}
	};*/
	/*************************************************/

	/**********************EqualOfK*****************/
	template <class Key>
	struct Equal
	{
		bool operator()(const Key& k1, const Key& k2)
		{
			return k1 == k2;
		}
	};
	/******************************************/

	/********/
	/*****迭代器*****/
	template <class Key, class T, class KOfT, class HashFunc, class EqualOfK, class Ptr, class Ref, class CopyOfT, class FreeOfT>
	class _HT_Iterator
	{
		typedef HashTable<Key, T, KOfT, HashFunc, EqualOfK, CopyOfT, FreeOfT> hashtbale;
		typedef HashTableNode<T> Node;
		typedef _HT_Iterator Self;

	private:
		hashtbale* _ht;
		Node* _node;

	public:
		_HT_Iterator(hashtbale* ht, Node* node) : _ht(ht), _node(node)
		{
		}
		Self& operator++() // 前置++
		{
			if (_node == nullptr)
				return *this;

			// 找下一个桶
			int pos = HashFunc()(KOfT()(_node->_val)) % _ht->_bucket_nums;

			_node = _node->_next;
			if (_node)
				return *this;

			for (int i = pos + 1; i < _ht->_bucket_nums; i++)
			{
				if (_ht->_tables[i])
				{
					_node = _ht->_tables[i];
					break;
				}
			}
		}
		Self operator++(int)
		{
			Self temp(_ht, _node);
			this->operator++();
			return temp;
		}
		Ref operator*()
		{
			return _node->_val;
		}
		Ptr operator->()
		{
			return &_node->_val;
		}
		bool operator==(const Self& other) const
		{
			return this->_node == other._node;
		}
		bool operator!=(const Self& other) const
		{
			return !(*this == other);
		}
	};

	/***************/
	void test_insert() {};
}